#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int T, n, a[200010];
bool dp[200010], sc[200010];
unordered_map<int, vector<int>> pre;

int find_prev(vector<int> &v, int l, int r, int val){
    if (l > r) return v[r];
    int mid = (l + r) / 2;
    if (v[mid] > val) return find_prev(v, l, mid-1, val);
    else if (v[mid] < val) return find_prev(v, mid+1, r, val);
    else{
        if (!mid) return 0;
        return v[mid-1];
    }
}

long long cost(int l, int i){
    long long cost = 0;
    for (int j=l+1; j<i; ++j){
        if (!sc[j]) continue;
        int aj = a[j];
        int p = find_prev(pre[aj], 0, pre[aj].size()-1, j);
        if (p && p != j-1){
            cost += a[p];
        }
    }
    return cost;
}

void simple(){
    long long ans = 0;
    for (int i=0; i<n; ++i) cin >> a[i];
    for (int i=0; i<(1<<n); ++i){
        long long cur = 0;
        for (int j=0; j<n; ++j){
            if (i & (1<<j)) dp[j] = 1;
            else dp[j] = 0;
        }
        for (int j=1; j<n; ++j){
            for (int k=j-1; k>=0; --k){
                if (a[j] == a[k] && dp[k] == dp[j]){
                    cur += a[j];
                    break;
                }
                if (dp[k] == dp[j]) break;
            }
        }
        ans = max(ans, cur);
    }
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(false);
    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
    cin >> T;
    for (int kkk=0; kkk<T; ++kkk){
        pre.clear();
        cin >> n;
        memset(dp, 0, sizeof(bool)*(n+2));
        memset(sc, 0, sizeof(bool)*(n+2));
        if (n <= 15){
            simple();
            continue;
        }
        long long ans = 0;
        for (int i=1; i<=n; ++i){
            cin >> a[i];
            if (!pre[a[i]].empty()){
                int l = pre[a[i]].back();
                long long c = cost(l, i);
                if (c < a[i]){
                    int rcolor = !dp[l];
                    for (int j=l+1; j<i; ++j){
                        dp[j] = rcolor;
                    }
                    dp[i] = dp[l];
                    sc[i] = 1; sc[l] = 1;
                    ans += a[i] - c;
                }
            }
            pre[a[i]].push_back(i);
        }
        //for (int i=1; i<=n; ++i) cout << dp[i] << " "; cout << endl;
        cout << ans << endl;
    }
    return 0;
}
